{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Decremental String Concatenation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizeConcatenatedLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串连接删减字母"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>words</code>&nbsp;，它包含 <code>n</code>&nbsp;个字符串。</p>\n",
    "\n",
    "<p>定义 <strong>连接</strong>&nbsp;操作&nbsp;<code>join(x, y)</code>&nbsp;表示将字符串&nbsp;<code>x</code> 和&nbsp;<code>y</code>&nbsp;连在一起，得到&nbsp;<code>xy</code>&nbsp;。如果&nbsp;<code>x</code>&nbsp;的最后一个字符与&nbsp;<code>y</code>&nbsp;的第一个字符相等，连接后两个字符中的一个会被&nbsp;<strong>删除</strong>&nbsp;。</p>\n",
    "\n",
    "<p>比方说&nbsp;<code>join(\"ab\", \"ba\") = \"aba\"</code>&nbsp;，&nbsp;<code>join(\"ab\", \"cde\") = \"abcde\"</code>&nbsp;。</p>\n",
    "\n",
    "<p>你需要执行&nbsp;<code>n - 1</code>&nbsp;次&nbsp;<strong>连接</strong>&nbsp;操作。令&nbsp;<code>str<sub>0</sub> = words[0]</code>&nbsp;，从&nbsp;<code>i = 1</code> 直到&nbsp;<code>i = n - 1</code>&nbsp;，对于第&nbsp;<code>i</code>&nbsp;个操作，你可以执行以下操作之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>令&nbsp;<code>str<sub>i</sub> = join(str<sub>i - 1</sub>, words[i])</code></li>\n",
    "\t<li>令&nbsp;<code>str<sub>i</sub> = join(words[i], str<sub>i - 1</sub>)</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>你的任务是使&nbsp;<code>str<sub>n - 1</sub></code>&nbsp;的长度<strong>&nbsp;最小&nbsp;</strong>。</p>\n",
    "\n",
    "<p>请你返回一个整数，表示&nbsp;<code>str<sub>n - 1</sub></code>&nbsp;的最小长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"aa\",\"ab\",\"bc\"]\n",
    "<b>输出：</b>4\n",
    "<strong>解释：</strong>这个例子中，我们按以下顺序执行连接操作，得到 <code>str<sub>2</sub></code> 的最小长度：\n",
    "<code>str<sub>0</sub> = \"aa\"</code>\n",
    "<code>str<sub>1</sub> = join(str<sub>0</sub>, \"ab\") = \"aab\"\n",
    "</code><code>str<sub>2</sub> = join(str<sub>1</sub>, \"bc\") = \"aabc\"</code> \n",
    "<code>str<sub>2</sub></code> 的最小长度为 4 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"ab\",\"b\"]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>这个例子中，str<sub>0</sub> = \"ab\"，可以得到两个不同的 str<sub>1</sub>：\n",
    "join(str<sub>0</sub>, \"b\") = \"ab\" 或者 join(\"b\", str<sub>0</sub>) = \"bab\" 。\n",
    "第一个字符串 \"ab\" 的长度最短，所以答案为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"aaa\",\"c\",\"aba\"]\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>这个例子中，我们按以下顺序执行连接操作，得到 <code>str<sub>2</sub>&nbsp;的最小长度：</code>\n",
    "<code>str<sub>0</sub> = \"</code>aaa\"\n",
    "<code>str<sub>1</sub> = join(str<sub>0</sub>, \"c\") = \"aaac\"</code>\n",
    "<code>str<sub>2</sub> = join(\"aba\", str<sub>1</sub>) = \"abaaac\"</code>\n",
    "<code>str<sub>2</sub></code> 的最小长度为 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 50</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;中只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [decremental-string-concatenation](https://leetcode.cn/problems/decremental-string-concatenation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [decremental-string-concatenation](https://leetcode.cn/problems/decremental-string-concatenation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"aa\",\"ab\",\"bc\"]', '[\"ab\",\"b\"]', '[\"aaa\",\"c\",\"aba\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        head, tail = '', ''\n",
    "        res = sum(len(w) for w in words)\n",
    "        \n",
    "        ctr = Counter()\n",
    "        \n",
    "        for w in words:\n",
    "            nxt = Counter()\n",
    "            for p, c in ctr.items():\n",
    "                nxt[p[0], w[-1]] = max(c + (p[-1] == w[0]), nxt[p[0], w[-1]])\n",
    "                nxt[w[0], p[-1]] = max(c + (w[-1] == p[0]), nxt[w[0], p[-1]])\n",
    "            \n",
    "            ctr = nxt\n",
    "            \n",
    "            if not ctr:\n",
    "                ctr[w[0], w[-1]] = 0\n",
    "        \n",
    "        # print(ctr)\n",
    "        return res - max(ctr.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        d = {}\n",
    "        \n",
    "        if len(words[0]) == 1:\n",
    "            d[words[0]] = 1\n",
    "        else:\n",
    "            d[words[0][0] + words[0][-1]] = len(words[0])\n",
    "        # print(words)\n",
    "        # print(d)\n",
    "        for word in words[1:]:\n",
    "            nd = {}\n",
    "            \n",
    "            a, b = word[0], word[-1]\n",
    "            \n",
    "            for i, j in d.items():\n",
    "                \n",
    "                k = a + i[-1]\n",
    "                if k not in nd:\n",
    "                    nd[k] = j + len(word) - (b == i[0]) \n",
    "                else:\n",
    "                    nd[k] = min(j + len(word) - (b == i[0]), nd[k])\n",
    "                \n",
    "                k = i[0] + b\n",
    "                if k not in nd:\n",
    "                    nd[k] = j + len(word) - (a == i[-1]) \n",
    "                else:\n",
    "                    nd[k] = min(j + len(word) - (a == i[-1]), nd[k])\n",
    "            d = nd\n",
    "            # print(d)\n",
    "        return min(d.values())\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        dp = [[inf] * 26 for _ in range(26)]\n",
    "\n",
    "        def f(c):\n",
    "            return ord(c) - ord('a')\n",
    "\n",
    "        word = words[0]\n",
    "\n",
    "        dp[f(word[0])][f(word[-1])] = len(word)\n",
    "\n",
    "        for word in words[1::]:\n",
    "            dp1 = [[inf] * 26 for _ in range(26)]\n",
    "            s,e = f(word[0]),f(word[-1])\n",
    "            for i in range(26):\n",
    "                for j in range(26):\n",
    "                    if dp[i][j] != inf:\n",
    "                        dp1[i][e] = min(dp1[i][e],dp[i][j] + len(word) - (1 if j == s else 0))\n",
    "                        dp1[s][j] = min(dp1[s][j],dp[i][j] + len(word) - (1 if e == i else 0))\n",
    "            dp = dp1\n",
    "        return min(min(v) for v in dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        d = {words[0][0] + words[0][-1]: len(words[0])}\n",
    "        for i in range(1, len(words)):\n",
    "            word = words[i]\n",
    "            temp = {}\n",
    "            for k, v in d.items():\n",
    "                kk = k[0] + word[-1]\n",
    "                vv = v + len(word)\n",
    "                if k[-1] == word[0]:\n",
    "                    vv -= 1\n",
    "                if kk in temp:\n",
    "                    if vv < temp[kk]:\n",
    "                        temp[kk] = vv\n",
    "                else:\n",
    "                    temp[kk] = vv\n",
    "                kk = word[0] + k[-1]\n",
    "                vv = len(word) + v\n",
    "                if word[-1] == k[0]:\n",
    "                    vv -= 1\n",
    "                if kk in temp:\n",
    "                    if vv < temp[kk]:\n",
    "                        temp[kk] = vv\n",
    "                else:\n",
    "                    temp[kk] = vv\n",
    "            d = temp\n",
    "        return min(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        pre = defaultdict(int)\n",
    "        pre[words[0][0] + words[0][-1]] = len(words[0])\n",
    "\n",
    "        for a in words[1:]:\n",
    "            cur = defaultdict(lambda: inf)\n",
    "            for b in pre:\n",
    "                # a+b\n",
    "                if a[-1] == b[0]:\n",
    "                    x = len(a) - 1 + pre[b]\n",
    "                else:\n",
    "                    x = len(a) +  pre[b]\n",
    "                cur[a[0] + b[-1]] = min(cur[a[0] + b[-1]], x)\n",
    "\n",
    "                # b+a\n",
    "                if b[-1] == a[0]:\n",
    "                    x = len(a) - 1 + pre[b]\n",
    "                else:\n",
    "                    x = len(a) + pre[b]\n",
    "                cur[b[0] + a[-1]] = min(cur[b[0] + a[-1]], x)\n",
    "            pre = cur\n",
    "\n",
    "        return min(pre.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = 1_000_000_007\n",
    "AORD = ord(\"a\")\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:        \n",
    "        dps = [[INF] * 26 for _ in range(26)]\n",
    "        headChar = ord(words[0][0]) - AORD\n",
    "        tailChar = ord(words[0][-1]) - AORD\n",
    "        dps[headChar][tailChar] = len(words[0])\n",
    "        \n",
    "        for word in words[1:]:\n",
    "            dpsNew = [[INF] * 26 for _ in range(26)]\n",
    "            wordhead = ord(word[0]) - AORD\n",
    "            wordtail = ord(word[-1]) - AORD\n",
    "            wordLen = len(word)\n",
    "            for head in range(26):\n",
    "                for tail in range(26):\n",
    "                    if dps[head][tail] == INF: continue\n",
    "                    diff = 1 if tail == wordhead else 0\n",
    "                    dpsNew[head][wordtail] = min(dpsNew[head][wordtail], dps[head][tail] + wordLen - diff)\n",
    "                    diff = 1 if head == wordtail else 0\n",
    "                    dpsNew[wordhead][tail] = min(dpsNew[wordhead][tail], dps[head][tail] + wordLen - diff)\n",
    "            dps = dpsNew\n",
    "\n",
    "        return min(min(li) for li in dps)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        f = {(words[0][0], words[0][-1]): len(words[0])}\n",
    "        n = len(words)\n",
    "        for i in range(1, n):\n",
    "            g = dict()\n",
    "            for (st, ed), v in f.items():\n",
    "                state = (st, words[i][-1])\n",
    "                g[state] = min(g.get(state, inf), v + len(words[i]) - int(ed == words[i][0]))\n",
    "                state = (words[i][0], ed)\n",
    "                g[state] = min(g.get(state, inf), v + len(words[i]) - int(st == words[i][-1]))\n",
    "            f = g\n",
    "        return min(v for k, v in f.items())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        def aa():\n",
    "            return inf\n",
    "        dp = { ( words[0][0],words[0][-1] ):len(words[0]) }  # (首，末)：最小长度\n",
    "        for i in words[1:]:\n",
    "            tmp_dic = collections.defaultdict(aa)\n",
    "            for tmp_key in dp.keys():\n",
    "                tmp_dic[ (tmp_key[0] , i[-1]) ] = min( dp[ tmp_key ] - (tmp_key[1] == i[0]) + len(i), tmp_dic[ (tmp_key[0] , i[-1]) ])\n",
    "                tmp_dic[ (i[0] , tmp_key[1]) ] = min( dp[ tmp_key ] - (tmp_key[0] == i[-1]) + len(i) ,tmp_dic[ (i[0] , tmp_key[1]) ] )\n",
    "            dp = tmp_dic\n",
    "        return min(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        f = {(words[0][0], words[0][-1]): len(words[0])}\n",
    "        n = len(words)\n",
    "        for i in range(1, n):\n",
    "            g = dict()\n",
    "            for (st, ed), v in f.items():\n",
    "                state = (st, words[i][-1])\n",
    "                g[state] = min(g.get(state, inf), v + len(words[i]) - int(ed == words[i][0]))\n",
    "                state = (words[i][0], ed)\n",
    "                g[state] = min(g.get(state, inf), v + len(words[i]) - int(st == words[i][-1]))\n",
    "            f = g\n",
    "        print(f)\n",
    "        return min(v for k, v in f.items())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        dp = [[float('inf') for _ in range(26)] for _ in range(26)]\n",
    "        dp[ord(words[0][0]) -  ord('a')][ord(words[0][- 1]) -  ord('a')] = len(words[0])\n",
    "        for w in words[1 : ]:\n",
    "            new = [[float('inf') for _ in range(26)] for _ in range(26)]\n",
    "            s, e = ord(w[0]) - ord('a'), ord(w[-1]) - ord('a')\n",
    "            for start in range(26):\n",
    "                for end in range(26):\n",
    "                    new[s][end] = min(new[s][end], len(w) + dp[start][end] - (e == start))\n",
    "                    new[start][e] = min(new[start][e], len(w) + dp[start][end] - (end == s))\n",
    "            dp = new \n",
    "        res = float('inf')\n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                res = min(res, dp[i][j])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        dp = [[float('inf') for _ in range(26)] for _ in range(26)]\n",
    "        dp[ord(words[0][0]) - ord('a')][ord(words[0][-1]) - ord('a')] = len(words[0])\n",
    "        for w in words[1:]:\n",
    "            new = [[float('inf') for _ in range(26)] for _ in range(26)]\n",
    "            s = ord(w[0]) - ord('a')\n",
    "            e = ord(w[-1]) - ord('a')\n",
    "            for start in range(26):\n",
    "                for end in range(26):\n",
    "                    new[start][e] = min(new[start][e], dp[start][end] + len(w) - (end == s))\n",
    "                    new[s][end] = min(new[s][end], dp[start][end] + len(w) - (start == e))\n",
    "            dp = new \n",
    "        res = float('inf')\n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                res = min(res, dp[i][j])\n",
    "        return res \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        st = [[-1] * 26 for _ in range(26)]\n",
    "        st[ord(words[0][0]) - ord('a')][ord(words[0][-1]) - ord('a')] = len(words[0])\n",
    "        n = len(words)\n",
    "        for i in range(1, n):\n",
    "            m = len(words[i])\n",
    "            next_st = [[-1] * 26 for _ in range(26)]\n",
    "            s = ord(words[i][0]) - ord('a')\n",
    "            e = ord(words[i][-1]) - ord('a')\n",
    "            for o_s in range(26):\n",
    "                for o_e in range(26):\n",
    "                    if st[o_s][o_e] >= 0:\n",
    "                        if o_e == s:\n",
    "                            if next_st[o_s][e] == -1:\n",
    "                                next_st[o_s][e] = m + st[o_s][o_e] - 1\n",
    "                            else:\n",
    "                                next_st[o_s][e] = min(m + st[o_s][o_e] - 1, next_st[o_s][e])\n",
    "                        else:\n",
    "                            if next_st[o_s][e] == -1:\n",
    "                                next_st[o_s][e] = m + st[o_s][o_e]\n",
    "                            else:\n",
    "                                next_st[o_s][e] = min(m + st[o_s][o_e], next_st[o_s][e])\n",
    "                        if e == o_s:\n",
    "                            if next_st[s][o_e] == -1:\n",
    "                                next_st[s][o_e] = m + st[o_s][o_e] - 1\n",
    "                            else:\n",
    "                                next_st[s][o_e] = min(next_st[s][o_e], m + st[o_s][o_e] - 1)\n",
    "                        else:\n",
    "                            if next_st[s][o_e] == -1:\n",
    "                                next_st[s][o_e] = m + st[o_s][o_e]\n",
    "                            else:\n",
    "                                next_st[s][o_e] = min(next_st[s][o_e], m + st[o_s][o_e])\n",
    "            st = next_st\n",
    "        min_val = float('inf')\n",
    "        for o_s in range(26):\n",
    "            for o_e in range(26):\n",
    "                if st[o_s][o_e] >= 0:\n",
    "                    min_val = min(min_val, st[o_s][o_e])\n",
    "        return min_val\n",
    "                    \n",
    "                        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        def get_ord(c):\n",
    "            return ord(c) - ord('a')\n",
    "        n = len(words)\n",
    "        dp = [[[1 << 30] * 26 for j in range(26)] for i in range(n)]\n",
    "        dp[0][get_ord(words[0][0])][get_ord(words[0][-1])] = len(words[0])\n",
    "        for k in range(1, n):\n",
    "            now = k & 1\n",
    "            pre = 1 ^ now\n",
    "            a = get_ord(words[k][0])\n",
    "            b = get_ord(words[k][-1])\n",
    "            wl = len(words[k])\n",
    "            for i in range(26):\n",
    "                for j in range(26):\n",
    "                    if dp[k - 1][i][j] == 1 << 30:\n",
    "                        continue\n",
    "                    dp[k][i][b] = min(dp[k - 1][i][j] + wl - (j == a), dp[k][i][b])\n",
    "                    dp[k][a][j] = min(dp[k - 1][i][j] + wl - (b == i), dp[k][a][j])\n",
    "                    # print(words[k], i, b, dp[now][i][b], a, j, dp[now][a][j])\n",
    "        return min(min(x) for x in dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        orda = ord('a')\n",
    "        dp = [[[inf] * 26 for _ in range(26)] for __ in range(len(words))]\n",
    "        dp[0][ord(words[0][0])-orda][ord(words[0][-1])-orda] = len(words[0])\n",
    "        for i in range(1, len(words)):\n",
    "            start = ord(words[i][0]) - orda \n",
    "            end = ord(words[i][-1]) - orda\n",
    "            l = len(words[i])\n",
    "            for j in range(26):  \n",
    "                for k in range(26):\n",
    "                    # current word is the first word\n",
    "                    if j != end:\n",
    "                        dp[i][start][k] = min(dp[i][start][k], dp[i-1][j][k] + l)\n",
    "                    else:\n",
    "                        dp[i][start][k] = min(dp[i][start][k], dp[i-1][j][k] + l - 1)\n",
    "                    # current word is the last word\n",
    "                    if k != start:\n",
    "                        dp[i][j][end] = min(dp[i][j][end], dp[i-1][j][k] + l)\n",
    "                    else:\n",
    "                        dp[i][j][end] = min(dp[i][j][end], dp[i-1][j][k] + l -1)\n",
    "                \n",
    "        ans = inf\n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                ans = min(dp[n-1][i][j], ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 50000\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        dp = [[[N] * 26 for _ in range(26)] for _ in range(n)]\n",
    "        dp[0][ord(words[0][0]) - ord('a')][ord(words[0][-1]) - ord('a')] = len(words[0])\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            i_b = ord(words[i][0]) - ord('a')\n",
    "            i_e = ord(words[i][-1]) - ord('a')\n",
    "            k = len(words[i])\n",
    "            for begin in range(26):\n",
    "                m = N\n",
    "                for end in range(26):\n",
    "                    if end == i_b:\n",
    "                        m = min(m, dp[i - 1][begin][end] + k - 1)\n",
    "                    else:\n",
    "                        m = min(m, dp[i - 1][begin][end] + k)\n",
    "                dp[i][begin][i_e] = min(dp[i][begin][i_e], m)\n",
    "\n",
    "            for end in range(26):\n",
    "                m = N\n",
    "                for begin in range(26):\n",
    "                    if begin == i_e:\n",
    "                        m = min(m, dp[i - 1][begin][end] + k - 1)\n",
    "                    else:\n",
    "                        m = min(m, dp[i - 1][begin][end] + k)\n",
    "                dp[i][i_b][end] = min(dp[i][i_b][end], m)\n",
    "\n",
    "        return min(dp[n - 1][i][j] for i in range(26) for j in range(26))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "        dp = [[[int(1e9)] * 26 for _ in range(26)] for _ in range(n)]\n",
    "        dp[0][ord(words[0][0]) - ord('a')][ord(words[0][-1]) - ord('a')] = len(words[0])\n",
    "\n",
    "        for i in range(n):\n",
    "            l = len(words[i])\n",
    "            x = ord(words[i][0]) - ord('a')\n",
    "            y = ord(words[i][-1]) - ord('a')\n",
    "            for j in range(26):\n",
    "                for k in range(26):\n",
    "                    if y == j:\n",
    "                        dp[i][x][k] = min(dp[i][x][k], dp[i-1][j][k] + l - 1)\n",
    "                    else:\n",
    "                        dp[i][x][k] = min(dp[i][x][k], dp[i-1][j][k] + l)\n",
    "                    if x == k:\n",
    "                        dp[i][j][y] = min(dp[i][j][y], dp[i-1][j][k] + l - 1)\n",
    "                    else:\n",
    "                        dp[i][j][y] = min(dp[i][j][y], dp[i-1][j][k] + l)\n",
    "        res = int(1e9)\n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                res = min(res, dp[n-1][i][j])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "        # dp[i][lw][rw] 到第i个单词，拼接字符串以lw开头rw结尾的最短拼接长度\n",
    "\n",
    "        dp = [[[inf for _ in range(26)] for _ in range(26)] for _ in range(n)]\n",
    "        map = {}\n",
    "        for i in range(26):\n",
    "            map[chr(i + ord('a'))] = i\n",
    "\n",
    "        dp[0][map[words[0][0]]][map[words[0][-1]]] = len(words[0])\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            word = words[i]\n",
    "            \n",
    "            for lw in range(26):\n",
    "                for rw in range(26):\n",
    "                    # 前后拼\n",
    "                    if map[word[0]] == rw:\n",
    "                        if dp[i][lw][map[word[-1]]] > dp[i-1][lw][rw] + len(word) - 1:\n",
    "                            dp[i][lw][map[word[-1]]] = dp[i-1][lw][rw] + len(word) - 1\n",
    "                    else:\n",
    "                        if dp[i][lw][map[word[-1]]] > dp[i-1][lw][rw] + len(word):\n",
    "                            dp[i][lw][map[word[-1]]] = dp[i-1][lw][rw] + len(word)\n",
    "                    \n",
    "                    # 后前拼\n",
    "                    if map[word[-1]] == lw:\n",
    "                        if dp[i][map[word[0]]][rw] > dp[i-1][lw][rw] + len(word) - 1:\n",
    "                            dp[i][map[word[0]]][rw] = dp[i-1][lw][rw] + len(word) - 1\n",
    "                    else:\n",
    "                        if dp[i][map[word[0]]][rw] > dp[i-1][lw][rw] + len(word):\n",
    "                            dp[i][map[word[0]]][rw] = dp[i-1][lw][rw] + len(word)\n",
    "                    \n",
    "        res = inf\n",
    "        for lw in range(26):\n",
    "            for rw in range(26):\n",
    "                if res > dp[-1][lw][rw]:\n",
    "                    res = dp[-1][lw][rw]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,e):\n",
    "            if i == n:return 0\n",
    "            word = words[i]\n",
    "            ans = dfs(i+1,(e[0],word[-1])) + len(words[i]) - int(e[-1] == word[0])\n",
    "            ans = min(ans,dfs(i+1,(word[0],e[-1])) + len(words[i]) - int(e[0] == word[-1]))\n",
    "            return ans\n",
    "\n",
    "        return dfs(1,(words[0][0],words[0][-1])) + len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        total = sum(len(w) for w in words)\n",
    "        n = len(words)\n",
    "        #print(words[0])\n",
    "        \n",
    "        # 1000 * 26 * 26\n",
    "        @cache\n",
    "        def dfs(index, start_char, end_char):\n",
    "            if index == n:\n",
    "                return 0\n",
    "            \n",
    "            ans = -inf\n",
    "            if words[index][0] == end_char:\n",
    "                ans = max(ans, 1 + dfs(index + 1, start_char, words[index][-1]))\n",
    "            else:\n",
    "                ans = max(ans, dfs(index + 1, start_char, words[index][-1])) \n",
    "                \n",
    "            if words[index][-1] == start_char:\n",
    "                ans = max(ans, 1 + dfs(index + 1, words[index][0], end_char))\n",
    "            else:\n",
    "                ans = max(ans, dfs(index + 1, words[index][0], end_char))\n",
    "            #print(index, start_char, end_char, ans)\n",
    "            return ans\n",
    "        \n",
    "        return total - dfs(1, words[0][0], words[0][-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(i: int, head: str, tail: str) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = inf\n",
    "            x = words[i]\n",
    "            return min(dfs(i + 1, head, x[-1]) + len(x) - (tail == x[0]), dfs(i + 1, x[0], tail) + len(x) - (head == x[-1]))\n",
    "        \n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n=len(words)\n",
    "        rem=collections.defaultdict(int)\n",
    "        def dfs(i,s,e):\n",
    "            if (i,s,e)in rem:\n",
    "                return rem[(i,s,e)]\n",
    "            if i==n:\n",
    "                return 0\n",
    "            ret=dfs(i+1,s,words[i][-1])+len(words[i])-int(words[i][0]==e)\n",
    "            ret=min(ret,dfs(i+1,words[i][0],e)+len(words[i])-int(words[i][-1]==s))\n",
    "            rem[(i,s,e)]=ret\n",
    "            return ret\n",
    "        return dfs(1,words[0][0],words[0][-1])+len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "\n",
    "        n=len(words)\n",
    "        @cache\n",
    "        def dfs(i,start,end):\n",
    "            if i==n:\n",
    "                return 0\n",
    "            word=words[i]\n",
    "            res=dfs(i+1,word[0],end)+len(word)-(word[-1]==start)\n",
    "            res=min(res,dfs(i+1,start,word[-1])+len(word)-(word[0]==end))\n",
    "            return res\n",
    "        return dfs(1,words[0][0],words[0][-1])+len(words[0])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(i,h,t):\n",
    "            if i == n: return 0\n",
    "            return min(len(words[i])-(words[i][-1]==h)+dfs(i+1,words[i][0],t),len(words[i])-(words[i][0]==t)+dfs(i+1,h,words[i][-1]))\n",
    "        return len(words[0]) + dfs(1,words[0][0],words[0][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(i, cl, cr):\n",
    "            if i == n: return 0\n",
    "            w, lw = words[i], len(words[i])\n",
    "            return min(dfs(i + 1, cl, w[-1]) + lw - (cr == w[0]), dfs(i + 1, w[0], cr) + lw - (w[-1] == cl))\n",
    "        return len(words[0]) + dfs(1, words[0][0], words[0][-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n=len(words)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i:int,start:str,end:str)->int:\n",
    "            if i==n:return 0\n",
    "            \n",
    "            res=dfs(i+1,start,words[i][-1])+len(words[i])-int(words[i][0]==end)\n",
    "            res=min(res,dfs(i+1,words[i][0],end)+len(words[i])-int(words[i][-1]==start))\n",
    "            \n",
    "            return res\n",
    "            \n",
    "        return dfs(1,words[0][0],words[0][-1])+len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(i: int, s: int, e: int) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            return min(dfs(i + 1, s, words[i][-1]) - int(words[i][0] == e), dfs(i + 1, words[i][0], e) - int(words[i][-1] == s)) + len(words[i])\n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,s,e):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            if words[i][0] == e:\n",
    "                ans = min(ans,dfs(i+1,s,words[i][-1])+len(words[i])-1)\n",
    "            if words[i][-1] == s:\n",
    "                ans = min(ans,dfs(i+1,words[i][0],e)+len(words[i])-1)\n",
    "            ans = min(ans,dfs(i+1,s,words[i][-1]) + len(words[i]))\n",
    "            ans = min(ans,dfs(i+1,words[i][0],e) + len(words[i]))\n",
    "            return ans\n",
    "        return dfs(1,words[0][0],words[0][-1]) + len(words[0])\n",
    "            \n",
    "\n",
    "        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def f(s,e,i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            r = inf\n",
    "            if words[i][0] == e:\n",
    "                r = min(r, len(words[i]) - 1 + f(s, words[i][-1], i+1))\n",
    "            else:\n",
    "                r = min(r, len(words[i]) + f(s, words[i][-1], i+1))\n",
    "            if words[i][-1] == s:\n",
    "                r = min(r, len(words[i]) - 1 + f(words[i][0],e, i+1))\n",
    "            else:\n",
    "                r = min(r, len(words[i]) + f(words[i][0],e, i+1))\n",
    "            return r\n",
    "        return len(words[0]) + f(words[0][0],words[0][-1], 1)\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        # 第 i 次操作，前面字符串开头为 s，末尾为e形成的最短长度        \n",
    "        @cache\n",
    "        def dfs(i: int, s: str, e: str) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            string = words[i]\n",
    "            res = dfs(i + 1, s, string[-1]) + len(string) - int(string[0] == e)\n",
    "            res = min(res, dfs(i + 1,string[0], e) + len(string) - int(string[-1] == s))\n",
    "            return res\n",
    "        n = len(words)\n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        le = len(words)\n",
    "        @cache\n",
    "        def dfs(c_beg, c_end, i):\n",
    "            if i == le:\n",
    "                return 0\n",
    "            # print(c_beg, c_end, i)\n",
    "            beg = len(words[i]) - (words[i][-1] == c_beg) + dfs(words[i][0], c_end, i + 1)\n",
    "            end = len(words[i]) - (words[i][0] == c_end) + dfs(c_beg, words[i][-1], i + 1)\n",
    "            # print(\"beg\", beg)\n",
    "            # print(\"end\", end)\n",
    "            return min(beg, end)\n",
    "        return len(words[0]) + dfs(words[0][0], words[0][-1], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        # 第 i 次操作，前面字符串开头为 s，末尾为e形成的最短长度        \n",
    "        @cache\n",
    "        def dfs(i: int, s: str, e: str) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            string = words[i]\n",
    "            res = dfs(i + 1, s, string[-1]) + len(string) - int(string[0] == e)\n",
    "            res = min(res, dfs(i + 1,string[0], e) + len(string) - int(string[-1] == s))\n",
    "            return res\n",
    "        n = len(words)\n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        @cache\n",
    "        def f(l, r, i):\n",
    "            if i == len(words): return 0\n",
    "            rnt = inf\n",
    "            if l == words[i][-1]: rnt = min(rnt, f(words[i][0], r, i+1) + len(words[i]) - 1)\n",
    "            if r == words[i][0]: rnt = min(rnt, f(l, words[i][-1], i+1) + len(words[i]) - 1)\n",
    "            return min(rnt, f(words[i][0], r, i+1) + len(words[i]), f(l, words[i][-1], i+1) + len(words[i]))\n",
    "        return f(words[0][0], words[0][-1], 1) + len(words[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        @cache\n",
    "        def dfs(left: str, right: str, i: int) -> int:\n",
    "            if i == len(words):\n",
    "                return len(words[0])\n",
    "            else:\n",
    "                return len(words[i]) + min(dfs(left, words[i][-1], i + 1) - (1 if right == words[i][0] else 0), dfs(words[i][0], right, i + 1) - (1 if left == words[i][-1] else 0))\n",
    "        return dfs(words[0][0], words[0][-1], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        # 第 i 次操作，前面字符串开头为 s，末尾为e形成的最短长度        \n",
    "        @cache\n",
    "        def dfs(i: int, s: str, e: str) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            string = words[i]\n",
    "            res = dfs(i + 1, s, string[-1]) + len(string) - int(string[0] == e)\n",
    "            res = min(res, dfs(i + 1,string[0], e) + len(string) - int(string[-1] == s))\n",
    "            return res\n",
    "        n = len(words)\n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n=len(words)\n",
    "\n",
    "      # ans=100000\n",
    "        @cache\n",
    "        def dfs(i,s,e):\n",
    "            #nonlocal ans\n",
    "            #rint()\n",
    "           # if l>=ans:\n",
    "                #return \n",
    "            if i==n:\n",
    "               \n",
    "               #print(s)\n",
    "                return 0\n",
    "            \n",
    "            ans=dfs(i+1,s,words[i][-1])+len(words[i])-int(words[i][0]==e)\n",
    "            ans=min(dfs(i+1,words[i][0],e)+len(words[i])-int(words[i][-1]==s),ans)\n",
    "            return ans\n",
    "       \n",
    "          \n",
    "        \n",
    "       \n",
    "        #dfs(0,0)\n",
    "        return dfs(1,words[0][0],words[0][-1])+len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, w: List[str]) -> int:\n",
    "        n=len(w)\n",
    "        @cache\n",
    "        def dfs(p,l,r):\n",
    "            if p>=n:\n",
    "                return 0\n",
    "            m=len(w[p])\n",
    "            return min(dfs(p+1,l,w[p][-1])+m+(-1 if w[p][0]==r else 0),dfs(p+1,w[p][0],r)+m+(-1 if w[p][-1]==l else 0))\n",
    "        return dfs(1,w[0][0],w[0][-1])+len(w[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        # 第 i 次操作，前面字符串开头为 s，末尾为e形成的最短长度        \n",
    "        @cache\n",
    "        def dfs(i: int, s: str, e: str) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            string = words[i]\n",
    "            res = dfs(i + 1, s, string[-1]) + len(string) - int(string[0] == e)\n",
    "            res = min(res, dfs(i + 1,string[0], e) + len(string) - int(string[-1] == s))\n",
    "            return res\n",
    "        n = len(words)\n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,s,e):\n",
    "            if i==n:\n",
    "                return 0\n",
    "            string=words[i]\n",
    "            res=dfs(i+1,s,string[-1])+len(string)-(string[0]==e)\n",
    "            res=min(res,dfs(i+1,string[0],e)+len(string)-(string[-1]==s))\n",
    "            return res\n",
    "        n=len(words)\n",
    "        return dfs(1,words[0][0],words[0][-1])+len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(i:int, ls:str, pr:str) -> int:\n",
    "            if i >= n: return 0\n",
    "            # 正\n",
    "            ans = dfs(i+1,words[i][-1], pr) + len(words[i]) + (-1 if words[i][0] == ls else 0)\n",
    "            #逆\n",
    "            ans = min(ans, dfs(i+1, ls, words[i][0]) + len(words[i]) + (-1 if words[i][-1] == pr else 0))\n",
    "            return ans\n",
    "        return dfs(1, words[0][-1], words[0][0]) + len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(s, e, idx):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            w = words[idx]\n",
    "            s1, e1 = w[0], w[-1]\n",
    "            ans1 = dfs(s, e1, idx + 1) - (e == s1)\n",
    "            ans2 = dfs(s1, e, idx + 1) - (e1 == s)\n",
    "            return min(ans1, ans2) + len(w)\n",
    "        return len(words[0]) + dfs(words[0][0], words[0][-1], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache \n",
    "        def dfs(i, s,e):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            ans = float('inf')\n",
    "            ans = min(ans, dfs(i+1, s, words[i][-1]) + len(words[i]) - int(e == words[i][0]))\n",
    "            ans = min(ans, dfs(i+1, words[i][0], e) + len(words[i]) - int(s == words[i][-1]))\n",
    "            #print(i,s,e, ans )\n",
    "            return ans \n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        # 第 i 次操作，前面字符串开头为 s，末尾为e形成的最短长度        \n",
    "        @cache\n",
    "        def dfs(i: int, s: str, e: str) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            string = words[i]\n",
    "            res = dfs(i + 1, s, string[-1]) + len(string) - int(string[0] == e)\n",
    "            res = min(res, dfs(i + 1,string[0], e) + len(string) - int(string[-1] == s))\n",
    "            return res\n",
    "        n = len(words)\n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "       n = len(words)\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int, l: int, r: int) -> int:\n",
    "          if i == n:\n",
    "             return 0\n",
    "          start = ord(words[i][0]) - ord('a')\n",
    "          end = ord(words[i][-1]) - ord('a')\n",
    "          return min(dfs(i + 1, l, end) + len(words[i]) - (start == r), dfs(i + 1, start, r) + len(words[i]) - (l == end))\n",
    "       return dfs(1, ord(words[0][0]) - ord('a'), ord(words[0][-1]) - ord('a')) + len(words[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(i, start_ch, end_ch):\n",
    "            if i == n: return 0\n",
    "            word, len_word = words[i], len(words[i])\n",
    "            first_ch, last_ch = word[0], word[-1]\n",
    "            res = dfs(i+1, start_ch, last_ch) + len_word - (end_ch == first_ch)\n",
    "            res  = min(res, dfs(i+1, first_ch, end_ch) + len_word - ( start_ch == last_ch))\n",
    "            return res\n",
    "        return len(words[0]) + dfs(1, words[0][0], words[0][-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        # 第 i 次操作，前面字符串开头为 s，末尾为e形成的最短长度        \n",
    "        @cache\n",
    "        def dfs(i: int, s: str, e: str) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            string = words[i]\n",
    "            res = dfs(i + 1, s, string[-1]) + len(string) - int(string[0] == e)\n",
    "            res = min(res, dfs(i + 1,string[0], e) + len(string) - int(string[-1] == s))\n",
    "            return res\n",
    "        n = len(words)\n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(i, cl, cr):\n",
    "            if i == n: return 0\n",
    "            #return min(dfs(i + 1, cl, words[i][-1]) + len(words[i]) - (cr == words[i][0]), dfs(i + 1, words[i][0], cr) + len(words[i]) - (words[i][-1] == cl))\n",
    "            w, lw = words[i], len(words[i])\n",
    "            return min(dfs(i + 1, cl, w[-1]) + lw - (cr == w[0]), dfs(i + 1, w[0], cr) + lw - (w[-1] == cl))\n",
    "        return len(words[0]) + dfs(1, words[0][0], words[0][-1])\n",
    "\n",
    "\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, s: str, e: str) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            string = words[i]\n",
    "            res = dfs(i + 1, s, string[-1]) + len(string) - int(string[0] == e)\n",
    "            res = min(res, dfs(i + 1,string[0], e) + len(string) - int(string[-1] == s))\n",
    "            return res\n",
    "        n = len(words)\n",
    "        return dfs(1, words[0][0], words[0][-1]) + len(words[0])        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeConcatenatedLength(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(s, e, idx):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            w = words[idx]\n",
    "            s1, e1 = w[0], w[-1]\n",
    "            ans1 = dfs(s, e1, idx + 1) + len(words[idx]) - (e == s1)\n",
    "            ans2 = dfs(s1, e, idx + 1) + len(words[idx]) - (e1 == s)\n",
    "            return min(ans1, ans2)\n",
    "        return len(words[0]) + dfs(words[0][0], words[0][-1], 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
